%\section{Proof of \Cref{thm:complexity of EQ}}\label{sec:proof of EQ}


We will use the following lower bound which can be derived using basic facts in communication complexity. We sketch its proof for completeness.
\begin{theorem}\label{thm:worst-partition EQ}
For some $\epsilon>0$, $R_{0,\epsilon}^{cc-pub}(\eq)\geq b$.
\end{theorem}
\begin{proof}[Proof sketch]
We need the following additional notations. Let $N^1(f)$ denote the {\em nondeterminic communication complexity} of computing $f$ (see, e.g., \cite[Definition 2.3]{KNbook}).
%
%Define $C^1(f)$ and $N^1(f)=\log_2 C^1(f)$ as in \cite[Definitions 2.1 and 2.3]{KNbook}.
%
It is well-known that $N^1(\eq)\geq b$ (see, e.g. \cite[Example 2.5]{KNbook}).
%
Note further that $R_{0,\epsilon}^{cc-pub}(f)\geq N^1(f)$ (see, e.g.,
\cite[Proposition 3.7]{KNbook}\footnote{We note that our notations are slightly different from \cite{KNbook}. It can be checked from \cite[Definitions 3.1 and 3.3]{KNbook} that the definition of $R_{0,\epsilon}^{rcc-pub}$ is the same as $R^1$, i.e. they correspond to the case where we allow an error only when $f(x,y)=1$.}). Thus, $R_{0,\epsilon}^{cc-pub}(\eq)\geq N^1(\eq)\geq b$ as claimed.
\end{proof}

\begin{proof}[Proof Lemma~\ref{lem:complexity of EQ}]
We will now prove that if $R_{0,\epsilon}^{rcc-pub}(\eq)< b/4-\sqrt{6b\ln b}$, then $R_{0,\epsilon}^{cc-pub}(\eq)<b$, thus contradicting Theorem~\ref{thm:worst-partition EQ}. This immediately implies that $R_{0,\epsilon}^{rcc-pub}(\eq)=\Omega(b)$, as claimed in Lemma~\ref{lem:complexity of EQ}. 
%
Let $\cA$ be a protocol in the random-partition model which requires strictly less than $b/4$ bits of communication. Alice and Bob simulates $\cA$ as follows. First, they use shared randomness to pick a random partition of $x$ and $y$, denoted by $\cP$. Let $S_B$ be the set of positions in $x$ that Bob receives in partition $\cP$. If $|S_B|>b/2+(1/2)\sqrt{6b\ln b}$, then they stop the simulation and answer $0$ (representing ``$x\neq y$''). Note that this could cause an error when $x=y$; however, by Chernoff's bound (e.g. \cite[Section~4.2.2]{MitzenmacherUpfalBook}), this happens with probability at most $2/b$.  If Alice and Bob do not stop the simulation, Alice sends to Bob bits in $x$ at positions in $S_B$. This causes a communication of $b/2+(1/2)\sqrt{6b\ln b}$ (note that Alice simply sends $|S_B|$ bits in order and Bob can figure out which bit belongs to which position since he also knows the partition $\cP$). Next, Bob checks whether bits in $x$ sent from Alice is the same as his bits (in the same position). If not, he immediately answers $0$ (``$x\neq y$''); otherwise, we let $S_A$ be the set of positions {\em not} in $S_B$ such that Alice receives bits in $y$ at positions in $S_A$. Bob checks if $|S_A|> (b-|S_B|)/2+(1/2)\sqrt{6b\ln b}$. If this is the case, then Alice and Bob stops the simulation and answer $0$. This again could cause an error but it happens with probability at most $2/b$ by Chernoff's bound. If this does not happen, Bob sends bits in $y$ at positions in $S_A$ to Alice. This causes at most $(b-|S_B|)/2+(1/2)\sqrt{6b\ln b}$ bits of communication. Then, Alice and Bob simulates $\cA$, which will finish after less than $b/4-\sqrt{6b\ln b}$ bits of communication and produces an answer that is $(\epsilon, 0)$-error. Alice and Bob use this answer as their answer. Combining with the previous errors, we have that Alice and Bob's answer is $(\epsilon+4/b, 0)$-error.\danupon{This proof is still a bit sketchy and needs a clean-up. In particular, we have to say why it is ok for $\cA$ not to see a completely random partition. The next sentence in the bracket tries to address this issue.} (This error comes from the worst-case scenario where $\cA$ could be always correct for the partitions that Alice and Bob stops. This gives the additional error of $4/b$.)
%
Moreover, the number of communication bits that their simulation requires is less than $|S_b|+(b-|S_b|)/2+(1/2)\sqrt{6b\ln b}+b/4-\sqrt{6b\ln b}$  which is less than $b$ since $|S_b|\leq b/2+(1/2)\sqrt{6b\ln b}$. This implies that $R_{0,\epsilon}^{cc-pub}(\eq)<b$ as desired. 

Note that in the reduction above Alice knows $x$ and Bob knows $y$. Thus, the claimed lower bound holds even when Alice and Bob have this information in addition to the random partition. 
\end{proof}

\endinput
